package cn.fxzhang.leetcode.no07;

import cn.fxzhang.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 783. 二叉搜索树节点最小距离
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * 本题跟530相同
 * 树中节点数目在范围 [2, 100] 内
 * 0 <= Node.val <= 105
 *
 * 类型：二叉树/遍历
 * 题解：遍历整棵树，将每个节点加入数组中，再对数组排序
 * 时间复杂度：O(NLogN)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 1 ms, 击败了26.90%
 * 内存消耗: 36.0 MB, 击败了68.21%
 *
 * 【简单】通过次数54,552提交次数92,661
 * @author 张晓帆
 * @date 2021/4/13
 */
public class P0783_Minimum_Distance_Between_Bst_Nodes {

    public int minDiffInBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        travel(root, list);
        Collections.sort(list);
        int result = Integer.MAX_VALUE;
        for (int i=1; i<list.size(); i++){
            if (list.get(i)-list.get(i-1) < result){
                result = list.get(i)-list.get(i-1);
            }
        }
        return result;
    }

    private void travel(TreeNode node, List<Integer> list) {
        if (node == null){
            return;
        }
        list.add(node.val);
        travel(node.left, list);
        travel(node.right, list);
    }
}
